package org.example.algorithm.array;

public class MinSubArrayLenSolution {
    /**
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     *
     * 找出该数组中满足其总和大于等于 target 的长度最小的
     * 子数组
     *  [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * 209. 长度最小的子数组
     * todo: 前缀和 + 二分查找
     * @param args
     */

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 5, 7};
        int target = 14;
        System.out.println(minSubArrayLen(target, nums));
    }

    public static int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int start = 0;
        int end = -1;
        int res = 0;
        int sum = 0;
        while (start < nums.length && end < nums.length) {
            if (sum >= target) {
                sum = sum - nums[start];
                start++;
            } else {
                end++;
                if (end < nums.length) {
                    sum = sum + nums[end];
                } else {
                    break;
                }
            }
            if (sum >= target) {
                if (res == 0) {
                    res = end - start + 1;
                } else {
                    res = Math.min(res, end-start+1);
                }
            }
        }
        return res;
    }

    /**
     * 暴力破解，数组较大时超时
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen2(int target, int[] nums) {
        int minCount = 0;
        for (int i=0;i< nums.length;i++) {
            int sum = 0;
            int j = i;
            int count = 0;
            while (sum < target) {
                sum += nums[j];
                count++;
                j++;
                if (j == nums.length) {
                    break;
                }
            }
            if (sum >= target) {
                if (minCount != 0) {
                    minCount = Math.min(count, minCount);
                } else {
                    minCount = count;
                }
            }
        }
        return minCount;
    }
}
